import java.util.ArrayList;
import java.util.List;

/**
* @description: 969. 煎饼排序
* @author hewei
* @date 2022/9/27 15:41
* @version 1.0
*/

public class PancakeSort {

    public List<Integer> pancakeSort(int[] arr) {
        int n = arr.length;
        int[] count = new int[n + 1];
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            count[arr[i]] = i;
        }
        for (int i = n; i >= 1; i--) {
            if (count[i] == i - 1) continue;
            int temp = count[i];
            for (int j = 1; j < i; j++) {
                if (count[j] < temp) {
                    count[j] = temp - count[j];
                }
                count[j] = i - 1 - count[j];
            }
            ans.add(temp + 1);
            ans.add(i);
        }
        return ans;
    }
}
